package offer.day22;

public class No36Copy_No36BinarySearchTreeConvertDouList {
    /*
     * 面试题36：二叉搜索树与双向链表     自己重新键入了一遍的
     * 题目：输入一棵二叉搜索树，将该二叉搜索树转换为一个排序的双向链表
     * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * 例如：输入10 -> (left)6     10 -> (right)14这棵二叉搜索树，
     * 		6 -> (left)4     6 -> (right)8
     * 		14 -> (left)12   14 -> (right)16
     * 则输出转换之后的排序双向链表： 4<-->6<-->8<-->10<-->12<-->14<-->16
     *
     *
     * 思路： 递归思想， 首先找到左子树的最后一个节点，
     * 			第一步：（<--操作）将根节点的左指针指向最后一个节点
     * 			第二步：（-->操作）将最后一个节点的右指针指向根节点
     * 			第三步：（下移操作）最后将根节点赋值为双向循环链表的最后一个节点（完成后移）
     * 			再次将最后一个节点传过去，然后完成上诉三步，在返回最后一个节点
     * 		返回最后一个节点后，要将指针重新指向根节点 使用while循环完成即可。
     * */
    public static void main(String[] args) {
        No36Copy_No36BinarySearchTreeConvertDouList  b = new No36Copy_No36BinarySearchTreeConvertDouList();

        BinaryTreeNode root = new BinaryTreeNode(10);
        BinaryTreeNode one = new BinaryTreeNode(6);
        BinaryTreeNode two = new BinaryTreeNode(14);
        BinaryTreeNode three = new BinaryTreeNode(4);
        BinaryTreeNode four = new BinaryTreeNode(8);
        BinaryTreeNode five = new BinaryTreeNode(12);
        BinaryTreeNode six = new BinaryTreeNode(16);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        System.out.println("二叉搜索树转换为双向链表的结果为：");

        BinaryTreeNode result = b.Convert(root);
        for(int i = 0;i < 7;i ++) {
            System.out.println("输出第"+i+"个节点："+result.val);
            result = result.right;
        }
    }

    public BinaryTreeNode Convert(BinaryTreeNode root) {
        BinaryTreeNode lastNode = null;
        BinaryTreeNode headNode = ConvertNode(root,lastNode);
        while(headNode != null && headNode.left != null) {
            headNode = headNode.left;
        }
        return headNode;
    }

    public BinaryTreeNode ConvertNode(BinaryTreeNode rootNode, BinaryTreeNode lastNode) {
        if(rootNode == null) {
            return null;
        }
        if(rootNode.left != null) {
            lastNode = ConvertNode(rootNode.left,lastNode);
        }
        rootNode.left = lastNode;
        if(lastNode != null) {
            lastNode.right = rootNode;
        }
        lastNode=rootNode;
        if(rootNode.right != null) {
            lastNode = ConvertNode(rootNode.right,lastNode);
        }
        return lastNode;
    }
}
